| Home Archive catalogue Bio of Turing More about Turing Codebreaking Artificial Intelligence Computer history Photo gallery Books on Turing Cambridge archive Links Copyright
|
The Church-Turing ThesisBy Jack Copeland© Copyright B.J. Copeland, June 2000There are various equivalent formulations of the Turing-Church thesis (which is also known as Turing's thesis, Church's thesis, and the Church-Turing thesis). One formulation of the thesis is that every effective computation can be carried out by a Turing machine. Effective MethodsThe Turing-Church thesis concerns the notion of an effective or mechanical method in logic and mathematics. 'Effective' and its synonym 'mechanical' are terms of art in these disciplines: they do not carry their everyday meaning. A method, or procedure, M, for achieving some desired result is called 'effective' or 'mechanical' just in case
A well-known example of an effective method is the truth table test for tautologousness. In practice, this test is unworkable for formulae containing a large number of propositional variables, but in principle one could apply it successfully to any formula of the propositional calculus, given sufficient time, tenacity, paper, and pencils. Statements that there is an effective method for achieving such-and-such a result are commonly expressed by saying that there is an effective method for obtaining the values of such-and-such a mathematical function. For example, that there is an effective method for determining whether or not any given formula of the propositional calculus is a tautology - e.g. the truth table method - is expressed in function-speak by saying that there is an effective method for obtaining the values of a function, call it T, whose domain is the set of formulae of the propositional calculus and whose value for any given formula x, written T(x), is 1 or 0 according to whether x is, or is not, a tautology. The Thesis and its HistoryThe notion of an effective method is an informal one, and attempts to characterise effectiveness, such as the above, lack rigour, for the key requirement that the method demand no insight or ingenuity is left unexplicated. One of Turing's achievements in his paper of 1936 was to present a formally exact predicate with which the informal predicate 'can be calculated by means of an effective method' may be replaced. Church did the same (1936a). The replacement predicates that Turing and Church proposed were, on the face of it, very different from one another, but they turned out to be equivalent, in the sense that each picks out the same set of mathematical functions. The Turing-Church thesis is the assertion that this set contains every function whose values can be obtained by a method satisfying the above conditions for effectiveness. (Clearly, if there were functions of which the informal predicate, but not the formal predicate, were true, then the latter would be less general than the former and so could not reasonably be employed to replace it.) When the thesis is expressed in terms of the formal concept proposed by Turing, it is appropriate to refer to the thesis also as 'Turing's thesis'; and mutatis mutandis in the case of Church. The formal concept proposed by Turing is that of computability by Turing machine. He argued for the claim (Turing's thesis) that whenever there is an effective method for obtaining the values of a mathematical function, the function can be computed by a Turing machine. The converse claim is easily established, for a Turing machine program is itself a specification of an effective method: a human being can work through the instructions in the program and carry out the operations called for without the exercise of any ingenuity or insight. If Turing's thesis is correct then talk about the existence and non-existence of effective methods can be replaced throughout mathematics and logic by talk about the existence or non-existence of Turing machine programs. Turing stated his thesis in numerous places, with varying degrees of rigour. The following formulation is one of the most accessible. Turing's thesis: 'LCMs [logical computing machines: Turing's expression for Turing machines] can do anything that could be described as "rule of thumb" or "purely mechanical".' (Turing 1948: 7.) He adds 'This is sufficiently well established that it is now agreed amongst logicians that "calculable by means of an LCM" is the correct accurate rendering of such phrases.' (Ibid.) Here are two other formulations of Turing's thesis. '[T]he "computable numbers" [the numbers whose decimal representations can be generated progressively by a Turing machine] include all numbers which would naturally be regarded as computable.' (Turing 1936: 249.) (As Turing explains: 'Although the subject of this paper is ostensibly the computable numbers, it is almost equally easy to define and investigate computable functions ... I have chosen the computable numbers for explicit treatment as involving the least cumbrous technique' (1936: 230).) 'It is my contention that these operations [the primitive operations of a Turing machine] include all those which are used in the computation of a number.' (Turing 1936: 232.) In order to understand these assertions exactly as Turing intended them it is necessary to bear in mind that when he uses the words 'computer', 'computable' and 'computation' he employs them as pertaining to human calculators. In 1936 'computers' were human clerks who worked in accordance with effective methods. These human computers did the sort of calculations nowadays carried out by computing machines, and many thousands of them were employed in commerce, government, and research establishments. The computable numbers and the computable functions are the numbers and functions that can be calculated by human computers (idealised to the extent of living forever and having access to unlimited quantities of paper and pencils). Turing introduced his thesis in the course of arguing that the Entscheidungsproblem, or decision problem, for the predicate calculus - posed by Hilbert (Hilbert and Ackermann 1928) - is unsolvable. Here is Church's account of the Entscheidungsproblem: 'By the Entscheidungsproblem of a system of symbolic logic is here understood the problem to find an effective method by which, given any expression Q in the notation of the system, it can be determined whether or not Q is provable in the system.' (Church 1936b: 41.) The truth table test is such a method for the propositional calculus. Turing showed that, given his thesis, there can be no such method for the predicate calculus. He proved formally that there is no Turing machine which can determine, in a finite number of steps, whether or not any given formula of the predicate calculus is a theorem of the calculus. So, given his thesis that if an effective method exists then it can be carried out by one of his machines, it follows that there is no such method to be found. Church had arrived at the same negative result a few months earlier, employing the concept of lambda-definability in place of computability by Turing machine. Church and Turing discovered the result quite independently of one another. Turing's method of obtaining it is rather more satisfying than Church's, as Church himself acknowledged in a review of Turing's work: 'computability by a Turing machine ... has the advantage of making the identification with effectiveness in the ordinary (not explicitly defined) sense evident immediately'. (1937a: 43.) (Another aspect in which their approaches differ is that Turing's concerns were rather more general than Church's, in that the latter considered only functions of positive integers (see below), whereas Turing described his work as encompassing 'computable functions of an integral variable or a real or computable variable, computable predicates, and so forth' (1936: 230). He intended to pursue the theory of computable functions of a real variable in a subsequent paper, but in fact did not do so.) Church used the (informal) expression 'effectively calculable' to indicate that there is an effective method for calculating the values of the function. He proposed that we 'define the notion ... of an effectively calculable function of positive integers by identifying it with the notion of a recursive function of positive integers (or of a lambda-definable function of positive integers)'. (1936a: 356.) The concept of a lambda-definable function is due to Church and Kleene (Church 1932, 1936a, 1941, Kleene 1935) and the concept of a recursive function to Godel and Herbrand (Godel 1934, Herbrand 1932). The class of lambda-definable functions and the class of recursive functions are identical. This was established in the case of functions of positive integers by Church and Kleene (Church 1936a, Kleene 1936). After learning of Church's proposal, Turing quickly established that the apparatus of lambda-definability and his own apparatus of computability are equivalent (1936: 263ff). Thus, in Church's proposal, the words 'recursive function of positive integers' can be replaced by the words 'function of positive integers computable by Turing machine'. Post referred to Church's identification of effective calculability with recursiveness as a 'working hypothesis', and quite properly criticised Church for masking this hypothesis as a definition. '[T]o mask this identification under a definition ... blinds us to the need of its continual verification.' (Post 1936: 105.) This, then, is the 'working hypothesis' that, in effect, Church proposed: Church's thesis: A function of positive integers is effectively calculable only if recursive. The reverse implication, that every recursive function of positive integers is effectively calculable, is commonly referred to as the converse of Church's thesis (although Church himself did not so distinguish, bundling both theses together in his 'definition'). If attention is restricted to functions of positive integers then Church's thesis and Turing's thesis are equivalent, in view of the previously mentioned results by Church, Kleene and Turing. The term 'Church-Turing thesis' seems to have been first introduced by Kleene, with a small flourish of bias in favour of Church: 'So Turing's and Church's theses are equivalent. We shall usually refer to them both as Church's thesis, or in connection with that one of its ... versions which deals with 'Turing machines' as the Church-Turing thesis.' (Kleene 1967: 232.) The Evidence for the ThesisMuch evidence has been amassed for the 'working hypothesis' proposed by Church and Turing in 1936. Perhaps the fullest survey is to be found in chapters 12 and 13 of Kleene (1952). In summary: (1) Every effectively calculable function that has been investigated in this respect has turned out to be computable by Turing machine. (2) All known methods or operations for obtaining new effectively calculable functions from given effectively calculable functions are paralleled by methods for constructing new Turing machines from given Turing machines. (3) All attempts to give an exact analysis of the intuitive notion of an effectively calculable function have turned out to be equivalent in the sense that each analysis offered has been proved to pick out the same class of functions, namely those that are computable by Turing machine. Because of the diversity of the various analyses, (3) is generally considered to be particularly strong evidence. Apart from the analyses already mentioned in terms of lambda-definability and recursiveness, there are analyses in terms of register machines (Shepherdson and Sturgis 1963), Post's canonical and normal systems (Post 1943, 1946), combinatory definability (Schonfinkel 1924, Curry 1929, 1930, 1932), Markov algorithms (Markov 1960), and Godel's notion of reckonability (Godel 1936, Kleene 1952). While there have from time to time been attempts to call the Turing-Church thesis into question (for example by Kalmar (1959); Mendelson (1963) replies), the summary of the situation that Turing gave in 1948 is no less true today: 'it is now agreed amongst logicians that "calculable by means of an LCM" is the correct accurate rendering' of the informal notion in question. Thesis MIt is important to distinguish between the Turing-Church thesis and the different proposition that whatever can be calculated by a machine can be calculated by a Turing machine. (The two propositions are sometimes confused.) Gandy (1980) terms the second proposition 'Thesis M'. Thesis M: Whatever can be calculated by a machine is Turing-machine-computable. Thesis M itself admits of two interpretations, according to whether the phrase 'can be calculated by a machine' is taken in the narrow sense of 'can be calculated by a machine that conforms to the physical laws (if not to the resource constraints) of the actual world', or in a wide sense that abstracts from the issue of whether or not the notional machine in question could exist in the actual world. The narrow version of thesis M is an empirical proposition whose truth-value is unknown. The wide version of thesis M is simply false. Various notional machines have been described which can calculate functions that are not Turing-machine-computable (for example, Abramson (1971), Copeland (1997), (1998c), da Costa and Doria (1991), (1994), Doyle (1982), Hogarth (1994), Pour-El and Richards (1979), (1981), Scarpellini (1963), Siegelmann and Sontag (1994), Stannett (1990), Stewart (1991); Copeland and Sylvan (1999) is a survey). Notice that the Turing-Church thesis does not entail thesis M; the truth of the Turing-Church thesis is consistent with the falsity of Thesis M (in both its wide and narrow forms). A thesis concerning effective methods - which is to say, concerning procedures of a certain sort that a human being unaided by machinery can carry out - carries no implication concerning the extent of the procedures that machines are capable of carrying out (since, for example, there might be, among a machine's repertoire of atomic operations, operations that no human being who is working effectively is able to perform). The above-mentioned evidence for the Turing-Church thesis is not also evidence for Thesis M. Bibliography
|
